package T2435;

public class Main {
}

class Solution {
    public static void main(String[] args) {
        int[][] grid = {{0,0}};
        System.out.println(numberOfPaths(grid, 5));
    }
    public static int numberOfPaths(int[][] grid, int k) {
        return f1(grid, k, grid.length, grid[0].length, 0, 0, 0);
    }

    /**
     * @param grid
     * @param k
     * @param n         行
     * @param m         列
     * @param i         第i行
     * @param j         第j列
     * @param remainder 剩余的路径和要可以整除k余remainder
     * @return 路径个数
     */
    public static int f1(int[][] grid, int k, int n, int m, int i, int j, int remainder) {
        if (i == n - 1 && j == m - 1) {
            return grid[i][j] % k == remainder ? 1 : 0;
        }
        int need = ((grid[i][j]%k)<remainder) ? (remainder-grid[i][j]%k):(grid[i][j]%k+k-remainder);
        int ans = 0;
        if(i+1<n) {
            ans = f1(grid, k, n, m, i+1, j, need);
        }
        if(j+1<m) {
            ans = ans + f1(grid, k, n, m, i, j+1, need);
        }
        return ans;
    }
}
